﻿//https://leetcode.cn/problems/find-all-anagrams-in-a-string/

//mine
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int n = p.size();
        int P[26];
        int hash[26];
        for (int i = 0; i < n; i++)
            P[p[i] - 97]++;
        vector<int> ret;
        int left = 0;
        for (int right = 0; right < s.size(); right++) {

            hash[s[right] - 97]++;

            if (right - left + 1 == n) {
                bool match = true;
                for (int i = 0; i < 26; i++) {
                    if (hash[i] != P[i]) {
                        match = false;
                        break;
                    }
                }
                if (match)
                    ret.push_back(left);
                hash[s[left] - 97]--;
                left++;
            }
        }
        return ret;
    }
};

//高效解法
vector<int> findAnagrams(string s, string p) {
    vector<int> ret;
    int hash1[26] = { 0 }; // 统计字符串 p 中每个字符出现的个数
    for (auto ch : p)
        hash1[ch - 'a']++;
    int hash2[26] = { 0 }; // 统计窗口⾥⾯的每一个字符出现的个数
    int m = p.size();
    for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
        char in = s[right];
        // 进窗口 + 维护 count
        if (++hash2[in - 'a'] <= hash1[in - 'a'])
            count++;
        if (right - left + 1 > m) // 判断
        {
            char out = s[left++];
            // 出窗口 + 维护 count
            if (hash2[out - 'a']-- <= hash1[out - 'a'])
                count--;
        }
        // 更新结果
        if (count == m)
            ret.push_back(left);
    }
    return ret;
}